
## 树

什么是树呢?在现实生活中有很多体现树的逻辑的例子。
  例如前面提到的小灰的“家谱”，就是一个“树”。
  再如企业里的职级关系，也是一个“树”。

  在数据结构中，树的定义如下。
树(tree)是n(n≥0)个节点的有限集。当n=0时，称为空树。在任意一个非 空树中，有如下特点。
1. 有且仅有一个特定的称为根的节点。
当n>1时，其余节点可分为m(m>0)个互不相交的有限集，每一个集合本身 又是一个树，并称为根的子树。

在上图中，节点1是根节点(root);节点5、6、7、8是树的末端，没有“孩 子”，被称为叶子节点(leaf)。图中的虚线部分，是根节点1的其中一个子树。


### 二叉树
二叉树(binary tree)是树的一种特殊形式。二叉，顾名思义，这种树的每 个节点最多有2个孩子节点。注意，这里是最多有2个，也可能只有1个，或者没有孩 子节点。
二叉树节点的两个孩子节点，一个被称为左孩子(left child)，一个被称为右孩 子(right child)。这两个孩子节点的顺序是固定的，就像人的左手就是左手，右手 就是右手，不能够颠倒或混淆。

此外，二叉树还有两种特殊形式，一个叫作满二叉树，另一个叫作完全二叉 树。  
一个二叉树的所有非叶子节点都存在左右孩子，并且所有叶子节点都在同一层
级上，那么这个树就是满二叉树。  

简单点说，满二叉树的每一个分支都是满的。
  什么又是完全二叉树呢?完全二叉树的定义很有意思。
对一个有n个节点的二叉树，按层级顺序编号，则所有节点的编号为从1到n。如 果这个树所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同，则这个 二叉树为完全二叉树。
  这个定义还真绕，看看下图就很容易理解了。

  二叉树可以用哪些物理存储结构来表达呢?
  1. 链式存储结构。
  2. 数组。


  假如节点4在数组中的下标是3，节点4是节点2的左孩子，节点2的下标可以直接 通过计算得出。
节点2的下标 = (3-1)/2 = 1 显然，对于一个稀疏的二叉树来说，用数组表示法是非常浪费空间的。
什么样的二叉树最适合用数组表示呢?
  我们后面即将学到的二叉堆，一种特殊的完全二叉树，就是用数组来存储的。

#### 二叉树的应用
二叉树包含许多特殊的形式，每一种形式都有自己的作用，但是其最主要的应 用还在于进行查找操作和维持相对顺序这两个方面

1. 查找
  二叉树的树形结构使它很适合扮演索引的角色。
这里我们介绍一种特殊的二叉树:二叉查找树(binary search tree)。光看名字 就可以知道，这种二叉树的主要作用就是进行查找操作。
  二叉查找树在二叉树的基础上增加了以下几个条件。
如果左子树不为空，则左子树上所有节点的值均小于根节点的值 如果右子树不为空，则右子树上所有节点的值均大于根节点的值 左、右子树也都是二叉查找树

对于一个节点分布相对均衡的二叉查找树来说，如果节点总数是n，那么搜索节 点的时间复杂度就是O(logn)，和树的深度是一样的。
  这种依靠比较大小来逐步查找的方式，和二分查找算法非常相似。




2. 维持相对顺序
  这一点仍然要从二叉查找树说起。二叉查找树要求左子树小于父节点，右子树
大于父节点，正是这样保证了二叉树的有序性。
因此二叉查找树还有另一个名字——二叉排序树(binary sort tree)。


这一切看起来很顺利，然而却隐藏着一个致命的问题。什么问题呢?下面请试 着在二叉查找树中依次插入9、8、7、6、5、4，看看会出现什么结果。

怎么解决这个问题呢?这就涉及二叉树的自平衡了。二叉树自平衡的方式有多 种，如红黑树、AVL树、树堆等。由于篇幅有限，本书就不一一详细讲解了，感兴趣 的读者可以查一查相关资料。

除二叉查找树以外，二叉堆也维持着相对的顺序。不过二叉堆的条件要宽松一 些，只要求父节点比它的左右孩子都大，这一点在后面的章节中我们会详细讲解。


那么，二叉树都有哪些遍历方式呢? 从节点之间位置关系的角度来看，二叉树的遍历分为4种。   
1. 前序遍历。
2. 中序遍历。
3. 后序遍历。
4. 层序遍历。   
从更宏观的角度来看，二叉树的遍历归结为两大类。  
1. 深度优先遍历(前序遍历、中序遍历、后序遍历)。   
2. 广度优先遍历(层序遍历)。  


3.2.2 深度优先遍历
  深度优先和广度优先这两个概念不止局限于二叉树，它们更是一种抽象的算法
思想，决定了访问某些复杂数据结构的顺序。在访问树、图，或其他一些复杂数据
结构时，这两个概念常常被使用到。
所谓深度优先，顾名思义，就是偏向于纵深，“一头扎到底”的访问方式。可 能这种说法有些抽象，下面就通过二叉树的前序遍历、中序遍历、后序遍历，来看 一看深度优先是怎么回事吧

















```java
public class Find {

    public static void main(String[] args) {

        Integer[] list = {1,9,4,9,1,0,0,1};

        int res = Find.index(list, 0);
        System.out.println(res); // 结果是5
    }


    public static <E> int index(E[] list, E target){
        for(int i = 0; i< list.length; i++)
            if(list[i].equals(target))
                return i;

        return -1;
    }

}
```

```js
class Find {
  static index(list, target) {
    for (let i = 0; i < list.length; i++) 
        if (list[i] === target) return i;

    return -1;
  }
}

const list = [1, 9, 4, 9, 1, 0, 0, 1];
const res = Find.index(list, 0);
console.log(res);
```







树是n个节点的有限集，有且仅有一个特定的称为根的节点。当n>1时，其余节 点可分为m个互不相交的有限集，每一个集合本身又是一个树，并称为根的子树。

## 二叉树
  二叉树是树的一种特殊形式，每一个节点最多有两个孩子节点。二叉树包含完全二叉树和满二叉树两种特殊形式。

  - 二叉树的遍历方式有几种
  根据遍历节点之间的关系，可以分为前序遍历、中序遍历、后序遍历、层序遍 历这4种方式;从更宏观的角度划分，可以划分为深度优先遍历和广度优先遍历两大 类。




## 二叉堆
二叉堆是一种特殊的完全二叉树，分为最大堆和最小堆。
  在最大堆中，任何一个父节点的值，都大于或等于它左、右孩子节点的值。
  在最小堆中，任何一个父节点的值，都小于或等于它左、右孩子节点的值。


## 优先队列
优先队列分为最大优先队列和最小优先队列。
  在最大优先队列中，无论入队顺序如何，当前最大的元素都会优先出队，这是
基于最大堆实现的。
  在最小优先队列中，无论入队顺序如何，当前最小的元素都会优先出队，这是
基于最小堆实现的。



